package m202405.d22;

import java.util.*;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/22 19:05
 */
public class Q994 {

    public static void main(String[] args) {
        Q994 q994 = new Q994();
        q994.orangesRotting(new int[][]{
                {2, 2},
                {1, 1},
                {0, 0},
                {2, 0}
        });
    }

    public int orangesRotting(int[][] grid) {
        Queue<Position> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new Position(i, j));
                }
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            queue = find(grid, queue);
            count++;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return Math.max(count - 1, 0);
    }

    private Queue<Position> find(int[][] grid, Queue<Position> queue) {
        Set<Position> rs = new HashSet<>();
        while (!queue.isEmpty()) {
            Position position = queue.poll();
            //上
            if (position.row > 0 && grid[position.row - 1][position.col] == 1) {
                add(grid, rs, position.row - 1, position.col);
            }
            //下
            if (position.row < grid.length - 1 && grid[position.row + 1][position.col] == 1) {
                add(grid, rs, position.row + 1, position.col);
            }
            //左
            if (position.col > 0 && grid[position.row][position.col - 1] == 1) {
                add(grid, rs, position.row, position.col - 1);
            }
            //右
            if (position.col < grid[0].length - 1 && grid[position.row][position.col + 1] == 1) {
                add(grid, rs, position.row, position.col + 1);
            }
        }
        return new LinkedList<>(rs);
    }

    private void add(int[][] grid, Set<Position> set, int row, int col) {
        Position position = new Position(row, col);
        set.add(position);
        grid[position.row][position.col] = 2;
    }


    private static class Position {
        int row;
        int col;

        Position(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Position position = (Position) o;
            return row == position.row && col == position.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
    }
}
